package main

import "fmt"

func insertionSort(arr []int) []int {
	for i := range arr {
		preIndex := i - 1
		current := arr[i]
		for preIndex >= 0 && arr[preIndex] > current {
			arr[preIndex+1] = arr[preIndex]
			preIndex -= 1
		}
		arr[preIndex+1] = current
	}

	return arr

}

func main() {

	arr := []int{1, 3, 5, 6}

	fmt.Println(insertionSort(arr))

}
